% Charles Douglas (cmd0028)
% Jeff Taylor (jwt0025)
% CSCI 4430

new_pop(0,_, []).
new_pop(PopSize,Limit, [R|Rs]):- 
	randomint(Limit, R), PS1 is (PopSize - 1),
	new_pop(PS1,Limit, Rs).

sqrt_breeding_fun(X,Y, R):- R=[RX,RY],RX is abs(2*X - Y), RY is abs(2*Y - X).
test_breeding_fun(X,Y, [X,Y]).

sqrt_fitness_fun(X, R):-
	Input=2008,
	Delta is (Input - X*X),
	ite(Delta >= 0, R=Delta, R=Input).

filter_fits(FitnessF,BreedingF,Randoms,Orgs, FittestChildren):-
	length(Orgs, L),
	breed(BreedingF, Randoms, Orgs, Children),
	map(FitnessF,Children,Fits),
	zip(Fits, Children, FitChildrenPairs),
	sort(FitChildrenPairs, SortedFitChildrenPairs),
	take(L, FittestChildrenPairs, SortedFitChildrenPairs),
	map(right, FittestChildrenPairs, FittestChildren).
	
evolve(_,_,_,0,_,P, P). 
evolve(_,_,_,_,_,[], []). 
evolve(FitnessF,BreedingF,RandLimit,Generations,Randoms,Orgs, R):-
	GenerationsLeft is Generations-1,
	filter_fits(FitnessF, BreedingF, Randoms, Orgs, Fits),
	length(Fits, L),
	new_pop(L,RandLimit,NewRandoms),
	evolve(FitnessF,BreedingF,RandLimit,GenerationsLeft,NewRandoms,Fits, R).

best([], none_found_alas).
best([X|_], X).

run_ga(Fitness,Breeding,PopSize,Generations,RandomLimit, R):-
	new_pop(PopSize, RandomLimit, Orgs),
	new_pop(PopSize, RandomLimit, Randoms),
	evolve(Fitness, Breeding, RandomLimit, Generations, Randoms, Orgs, R).
	
ga(R):-
	Fitness=sqrt_fitness_fun,
	Breeding=sqrt_breeding_fun,
	Popsize=100,
	Generations=10,
	RandomLimit=100,
	run_ga(Fitness,Breeding,Popsize,Generations,RandomLimit, R).
	
main(R):-
	ga(Orgs),
	best(Orgs, R).

breed(F, Randoms, Orgs, R):-
	gender_split(Orgs, Randoms, (Males, Females)),
	breed_groups(F, Males, Females, R).

breed_groups(_, [], _, []).
breed_groups(_, _, [], []).
breed_groups(F, [Male|Males], [Female|Females], R):-
	call(F, Male, Female, Children),
	breed_groups(F, Males, Females, OtherChildren),
	append(Children, OtherChildren, R).	


gender_split(Orgs, Randoms, R):-
	pair(Males, Females, R),
	gender(1, Randoms, Orgs, Females),
	gender(0, Randoms, Orgs, Males).

gender(_, _, [], []).
gender(G,[Random|Randoms],[Org|Orgs], Result) :-
	ite(gender_s(G,Random,Org, R), Result=[R|Rs], Result=Rs),
	gender(G,Randoms,Orgs, Rs).

gender_s(G,Random,Org, Org):-G is mod(Random, 2). 

% Utilities!
ite(Cond,Then,_Else):-call(Cond),!,call(Then).
ite(_Cond,_Then,Else):-call(Else).

randomint(Limit,I):-
  random(X),
  LiftX is Limit*X,
  I is truncate(LiftX).

pair(X,Y,(X,Y)).

left((X, _), X).
right((_,Y), Y).

map(_,[], []).
map(F, [X|Xs], [R|Rs]):-
	call(F, X, R),
	map(F, Xs, Rs).

map2(_,[],_,[]).
map2(_,_,[],[]).
map2(F, [X|Xs], [Y|Ys], [R|Rs]):-
	call(F, X, Y, R),
	map2(F, Xs, Ys, Rs).

zip(Xs, Ys, R):-
	map2(pair, Xs, Ys, R).
	
take(_, [], []).
take(0, _, []).
take(N, [X|Xs], [R|Rs]):-
	R=X,
	N1 is N-1,
	take(N1, Xs, Rs).
